希尔排序

1. 希尔排序又称最小增量排序。
2. 是对插入排序的优化。
3. 基本思想：选取合理的增量，经过一轮排序后，就会让序列大致有序，然后再不断缩小增量，增量每次缩小为原来的一半，进行插入排序，直到增量为1，排序结束。
4. 直接插入排序其实就是增量为1的希尔排序。
5. 第一次增量选取长度的一半。

public class ShellsSort {
    public static void main(String[] args) {
        int[] arr = {46, 55, 13, 42, 17, 94, 5, 70};
        int j;

        // 初始增量为数组长度的一半，每一趟除以2
        for (int h = arr.length / 2; h > 0; h /= 2) {
            // 选择排序
            for (int i = h; i < arr.length; i++) {
                Comparable<Integer> tmp = arr[i];
                for (j = i; j >= h && tmp.compareTo(arr[j - h]) < 0; j -= h) {
                    arr[j] = arr[j - h];
                }
                arr[j] = (int) tmp;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}